/*
 * 1066. 二叉树的前序遍历
 * 给出一棵二叉树，返回其节点值的前序遍历。
 * https://www.lintcode.com/problem/binary-tree-preorder-traversal/description
 * 
 * 样例
 * 给出一棵二叉树 {1,#,2,3},
 *  	1
 *  	 \
 *  	  2
 *  	 /
 *       3
 * 返回 [1,2,3].
 * 
 * 挑战
 * 你能使用非递归实现么？
 * 
 * 2018.06.16 @jeyming
 */

package binary_tree_preorder_traversal_1066;

import java.util.ArrayList;
import java.util.List;

/**
 *Definition of TreeNode:
 */
class TreeNode {
	public int val;
	public TreeNode left, right;
	public TreeNode(int val) {
		this.val = val;
		this.left = this.right = null;
	}
}

public class Binary_tree_preorder_traversal_1066 {
    /**
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
	List<Integer> list;
	
	public void preOrder(TreeNode root) {
		if(root != null) {
			list.add(root.val);
			preOrder(root.left);
			preOrder(root.right);
		}
	}
	
    public List<Integer> preorderTraversal(TreeNode root) {
        // write your code here
    	list = new ArrayList<Integer>();
    	//递归
    	preOrder(root);
    	return list;
    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
